package com.peng.leetcode.list;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * GetIntersectionNode
 * 编写一个程序，找到两个单链表相交的起始节点。
 *
 * @author: lupeng6
 * @create: 2020/12/31 14:42
 */
public class GetIntersectionNode {

    public static void main(String[] args) {

    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Deque<ListNode> dequeA = new LinkedList<>();
        Deque<ListNode> dequeB = new LinkedList<>();
        ListNode current1 = headA;
        ListNode current2 = headB;

        while (current1 != null) {
            dequeA.offer(current1);
            current1 = current1.next;
        }

        while (current2 != null) {
            dequeB.offer(current2);
            current2 = current2.next;
        }
        ListNode first = null;
        while (!dequeA.isEmpty() && !dequeB.isEmpty()) {
            ListNode a = dequeA.pollLast();
            ListNode b = dequeB.pollLast();
            if (a == b) {
                first = a;
            } else {
                break;
            }
        }
        return first;
    }

    public static ListNode getIntersectionNodeByHash(ListNode headA, ListNode headB) {
        HashSet<ListNode> nodes = new HashSet<>();
        ListNode currentA = headA;
        while (currentA != null) {
            nodes.add(currentA);
            currentA = currentA.next;
        }


        ListNode currentB = headB;
        while (currentB != null) {
            if (nodes.contains(currentB)) {
                return currentB;
            }
            currentB = currentB.next;
        }
        return null;
    }
}
